// https://leetcode.cn/problems/repeated-dna-sequences/
// Created by ade on 2022/8/25.
//
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    const int L = 10;

    vector <string> findRepeatedDnaSequences(string s) {
        unordered_map<string, int> m = {};
        vector <string> res = {};
        for (int i = 0; i < s.size() - L; i++) {
            string tmp = s.substr(i, L);
            m[tmp]++;
            if (m[tmp] > 1) {
                res.push_back(tmp);
            }
        }
        return res;
    }
};

int main() {
    Solution so;
    string s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
    auto res = so.findRepeatedDnaSequences(s);
    for (auto i : res) {
        cout << i << endl;
    }
    return 0;
}